package com.github.yangyishe.p200;

import java.util.*;

/**
 * 131. 分割回文串
 * https://leetcode.cn/problems/palindrome-partitioning/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
 * 回文串
 *  。返回 s 所有可能的分割方案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 *
 * 输入：s = "a"
 * 输出：[["a"]]
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 */
public class Problem131 {
    public static void main(String[] args) {
        String s="aab";

        Problem131 problem131 = new Problem131();
        List<List<String>> partition = problem131.partition(s);
        System.out.println("partition = " + partition);
    }

    /**
     * 思路：
     * 需要设计一种遍历方式。
     * 判断一个长度为n的字符串的子字符串，一共有n*(n+1)/2种子字符串需要判断
     * 每个字符串可表示为[start,end]，其中start为开始指针，end为结束指针。
     * 要判断[start,end]是否构建回文字符串，先判断start&lt；end是否成立。
     * 如果成立，则先判断[start+1,end-1]是否构成回文字符串，而由于该长度较小，必定在之前已经判断过了（也可能长度为0或1，则直接pass）；这之后再判断char[start]==char[end]是否成立接口。
     *
     *
     * 集合[start,end]的集合（start小于end）,必定等于整个元素[start,i]加上子集合[i+1,end]的情况
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        char[] chars = s.toCharArray();
        for(int step=0;step<chars.length;step++){
            for(int start=0;start+step<chars.length;start++){
                calcHuiwen(chars,start,start+step);
            }
        }

        return calcSubPartition(s,0);
    }



    private Map<Integer, Map<Integer,Boolean>> start2End2SuccessMap =new HashMap<>();

    private void calcHuiwen(char[] chars, int start, int end){
        start2End2SuccessMap.putIfAbsent(start,new HashMap<>());
        if(start>=end){
            start2End2SuccessMap.get(start).put(end,true);
            return;
        }
        if(!start2End2SuccessMap.get(start+1).containsKey(end-1)){
            calcHuiwen(chars,start+1,end-1);
        }
        Boolean beforeSuccess = start2End2SuccessMap.get(start+1).get(end-1);
        if(!beforeSuccess){
            start2End2SuccessMap.get(start).put(end,false);
            return;
        }
        boolean currentSuccess = chars[start] == chars[end];

        start2End2SuccessMap.get(start).put(end,currentSuccess);
    }

    private Map<Integer,List<List<String>>> start2PartitionListMap=new HashMap<>();

    private List<List<String>> calcSubPartition(String s,int start){
        if(start2PartitionListMap.get(start)!=null){
            return start2PartitionListMap.get(start);
        }
        if(start==s.length()-1){
            List<List<String>> resultList=Arrays.asList(Arrays.asList(s.substring(start)));
            start2PartitionListMap.put(start,resultList);
            return resultList;
        }
        List<List<String>> allList=new ArrayList<>();
        for(int i=start;i<s.length();i++){
            Boolean success = start2End2SuccessMap.get(start).get(i);
            if(success){
                String substring = s.substring(start, i+1);
                if(i==s.length()-1){
                    allList.add(Arrays.asList(substring));
                }else{
                    List<List<String>> nextList=calcSubPartition(s,i+1);
                    for (List<String> eachList : nextList) {
                        List<String> newList=new ArrayList<>();
                        newList.add(substring);
                        newList.addAll(eachList);
                        allList.add(newList);
                    }
                }
            }

        }
        start2PartitionListMap.put(start,allList);

        return allList;
    }

}
